package leetcode.calc._06_07;

import org.springframework.util.Assert;

import java.util.LinkedList;

/**
 * 给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
 * <p>
 * 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
 * <p>
 * 此外，你可以假设该网格的四条边均被水包围。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：grid = [
 * ['1','1','1','1','0'],
 * ['1','1','0','1','0'],
 * ['1','1','0','0','0'],
 * ['0','0','0','0','0']
 * ]
 * 输出：1
 * 示例 2：
 * <p>
 * 输入：grid = [
 * ['1','1','0','0','0'],
 * ['1','1','0','0','0'],
 * ['0','0','1','0','0'],
 * ['0','0','0','1','1']
 * ]
 * 输出：3
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/number-of-islands
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _06_28_200_岛屿数量 {
    public static void main(String[] args) {
        Solution sol = new _06_28_200_岛屿数量().new Solution();

        if (true) {
            char[][] grid = {
                new char[]{'1', '1', '1'},
                new char[]{'0', '1', '0'},
                new char[]{'1', '1', '1'},
            };
            int res = sol.numIslands(grid);
            int rel = 1;
            Assert.isTrue(res == rel, String.format("%s!=%s", res, rel));
        }
        if (true) {
            char[][] grid = {
                new char[]{'1', '1', '1', '1', '0'},
                new char[]{'1', '1', '0', '1', '0'},
                new char[]{'1', '1', '0', '0', '0'},
                new char[]{'0', '0', '0', '0', '0'},
            };
            int res = sol.numIslands(grid);
            int rel = 1;
            Assert.isTrue(res == rel, String.format("%s!=%s", res, rel));
        }

        if (true) {
            char[][] grid = {
                new char[]{'1', '1', '0', '0', '0'},
                new char[]{'1', '1', '0', '0', '0'},
                new char[]{'0', '0', '1', '0', '0'},
                new char[]{'0', '0', '0', '1', '1'},
            };
            int res = sol.numIslands(grid);
            int rel = 3;
            Assert.isTrue(res == rel, String.format("%s!=%s", res, rel));
        }
    }

    class Solution {
        public int numIslands(char[][] grid) {
            // 广度优先算法
            // 记录数量
            int count = 0;
            // 创建一个 LinkedList
            LinkedList<Integer> queque = new LinkedList<>();
            int rowC = grid.length;
            int colC = grid[0].length;
            for (int row = 0; row < rowC; row++) {
                char[] rowGrid = grid[row];
                for (int col = 0; col < colC; col++) {
                    // 判断 1, 进入 List, 并 + 1
                    if (rowGrid[col] == '1') {
                        count++;
                        // 添加队列, 队列赋值0
                        queque.add(row * colC + col);

                    }
                    // 刷成0, 先进先出
                    while (!queque.isEmpty()) {
                        Integer num = queque.remove();
                        int r = num / colC;
                        int c = num % colC;
                        grid[r][c] = '0';
                        if (r > 0 && grid[r - 1][c] == '1') {
                            queque.add((r - 1) * colC + c);
                        }
                        if (r + 1 < rowC && grid[r + 1][c] == '1') {
                            queque.add((r + 1) * colC + c);
                        }
                        if (c > 0 && grid[r][c - 1] == '1') {
                            queque.add(r * colC + c - 1);
                        }
                        if (c + 1 < colC && grid[r][c + 1] == '1') {
                            queque.add(r * colC + c + 1);
                        }
                    }
                }
            }
            return count;
        }
    }
}
